package datastructure.sort;

/**
 *
 *
 * @author Lei Zhang
 */
public class QuickSort {
  public static void sort(int[] arr, int startIndex, int endIndex) {
    if (arr == null || arr.length == 0) {
      return;
    }

    int pivot = (endIndex + startIndex) / 2;
    int value = arr[pivot];

    int i = startIndex;
    int j = endIndex;

    while (i <= j) {

      while (arr[i] < value) {
        i++;
      }

      while (arr[j] > value) {
        j--;
      }

      if (i <= j) {
        exchange(arr, i, j);
        i++;
        j--;
      }
    }

    if (startIndex < i - 1) {
      sort(arr, startIndex, i - 1);
    }

    if (endIndex > i) {
      sort(arr, i, endIndex);
    }

  }

  private static void exchange(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

  public static void main(String args[]) {

    int[] arr = {5,
      7,
      1,
      19,
      8,
      90,
      3,
      2,
      78};

    QuickSort.sort(arr, 0, arr.length - 1);

    for (int i = 0; i < arr.length; i++) {
      System.out.println(arr[i]);
    }

  }
}
